"""
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。
s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

递归法，一个一个比找到节点值相等的之后，再递归进行判断是否数相等，要注意出口的设计
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        flag = False
        if not s or not t: return False
        if s.val == t.val:
            flag = self.isEqual(s, t)
        if not flag:
            flag = self.isSubtree(s.left, t)
        if not flag:
            flag = self.isSubtree(s.right, t)
        return flag

    def isEqual(self, a, b):
        if not b and not a: return True
        if not a or not b: return False
        if a.val == b.val:
            left = self.isEqual(a.left, b.left)
            right = self.isEqual(a.right, b.right)
            return left and right
        else:
            return False


a1 = TreeNode(1)
a0 = TreeNode(0)
a2 = TreeNode(2)
a3 = TreeNode(3)
a4 = TreeNode(4)
a5 = TreeNode(5)

a1.left = a0
a4.left = a1
a4.right = a2
a3.left = a4
a3.right = a5

b1 = TreeNode(1)
b4 = TreeNode(4)
b2 = TreeNode(2)
b4.left = b1
b4.right = b2

s = Solution()
print(s.isSubtree(a3, b4))


